//字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
//
//
//
// 示例：
//
//
//输入：S = "ababcbacadefegdehijhklij"
//输出：[9,7,8]
//解释：
//划分结果为 "ababcbaca", "defegde", "hijhklij"。
//每个字母最多出现在一个片段中。
//像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
//
//
//
//
// 提示：
//
//
// S的长度在[1, 500]之间。
// S只包含小写字母 'a' 到 'z' 。
//
// Related Topics 贪心 哈希表 双指针 字符串 👍 785 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.List;

class 划分字母区间 {
    public static void main(String[] args) {
        Solution solution = new 划分字母区间().new Solution();
        String S = "ababcbacadefegdehijhklij";
        List<Integer> integers = solution.partitionLabels(S);
        System.out.println(integers);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public List<Integer> partitionLabels(String S) {
            //每个字母最后一次出现的位置
            char[] str = S.toCharArray();
            int[] far = new int[26];
            for (int i = 0; i < str.length; i++) {
                far[str[i] - 'a'] = i;
            }

            //右滑指针超过right 就是切割点
            List<Integer> ans = new ArrayList<>();
            int left = 0;
            int right = far[str[0] - 'a'];//a出现的最右侧的位置
            for (int i = 1; i < str.length; i++) {
                if (i > right) {
                    ans.add(right - left + 1);
                    left = i;
                }
                right = Math.max(right, far[str[i] - 'a']);
            }
            ans.add(right - left + 1);
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
